Average-Case Analyse parametrisierter & probabilistischer...
Ein Problem, stellt sich als NP-vollständig heraus. Sehr wahrscheinlich gibt es also keinen schnellen Algorithmus, der das Problem löst. Was also tun? Sich mit dieser eher unbefriedigenden Antwort der klassischen (Worst-Case)- Komplexitätstheorie abzugeben und die Aufgabe ungelöst zurückzulassen, ist insbesondere in der Praxis oft kein denkbarer Umgang mit der Situation. Doch es gibt einige Ansätze, wie man sich dennoch diesen ...